package com.fosss.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 * 使用二分查找的前提是数组有序
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,5,5,6,7,8,9,55};

        //测试不能找重复值的
        int result = binarySearch(arr, 0, arr.length-1, 1);
        System.out.println(result);

        //测试能找重复值的
        List<Integer> results = binarySearch2(arr, 0, arr.length - 1, 5);
        System.out.println(results);
    }

    /**
     * 不能查找到重复的值
     * @param arr 有序的升序的数组
     * @param left 左边界
     * @param right 右边界
     * @param value 要查找的值
     * @return   查找到的索引
     */
    public static int binarySearch(int[] arr,int left,int right,int value){

        if(left>right){
            //说明没有找到
            return -1;
        }
        int mid=(left+right)/2;
        int midValue=arr[mid];
        if(value<midValue){
            //向左递归
            return binarySearch(arr,left,mid-1,value);
        } else if (value > midValue) {
            //向右递归
            return binarySearch(arr,mid+1,right,value);
        }else {
            //找到了，直接返回索引
            return mid;
        }

    }

    /**
     * 改进
     * 能查找到重复的值
     * @param arr 有序的升序的数组
     * @param left 左边界
     * @param right 右边界
     * @param value 要查找的值
     * @return   查找到的索引
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int value){
        int mid=(left+right)/2;
        int midValue=arr[mid];
        if(left>right){
            //说明没有找到
            return new ArrayList<>();
        }

        if(value<midValue){
            //向左递归
            binarySearch2(arr,left,mid-1,value);
        } else if (value > midValue) {
            //向右递归
            binarySearch2(arr,mid+1,right,value);
        }else {
            //找到了，找到重复的值，存放到集合中
            List<Integer> values=new ArrayList<>();
            values.add(mid);//先将已经找到的索引添加到集合中，如果向保持顺序的话，可以放到下面两个查找中间

            //向左找
            int temp=mid-1;
            while (true){
                if(temp<0||arr[temp]!=arr[mid]){
                    break;
                }
                values.add(temp);
                temp--;
            }

            //向右找
            temp=mid+1;
            while (true){
                if(temp>arr.length-1||arr[temp]!=arr[mid]){
                    break;
                }
                values.add(temp);
                temp++;
            }

            //将存有所有索引的集合返回
            return values;
        }
        return new ArrayList<>();
    }
}









